import java.util.HashMap;
import java.util.List;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class SFT {

	public static List<Integer> SFTAlgorithm(int N, double intau, double delta, Oracle f, double norm){
		double tau = 8*intau;
		List<Integer> coff = new LinkedList<Integer>();
		List<Set<Integer>> abSets = generateQueries(N, tau / 36, norm, delta, tau, f);
		Set<Integer> Q = getQ(abSets, N);
		Map<Integer, Complex> queries = getQueriesValues(Q, f);
		coff = fixedQueriesSFT(N, tau, abSets, queries);
		return coff;
	}
	
	private static double getDelta(double delta, double tau, int N, Oracle f){
		return delta / (Math.pow((f.euclideanNormSquared(N) / tau), 1.5)) * ((Math.log(N) / Math.log(2)));
	}
	
	private static double getEta(double gamma, double norm){
		return Math.min(gamma, Math.min(Math.sqrt(gamma), (gamma / norm)));
	}
	
	private static List<Set<Integer>> generateQueries(int N, double gamma, double norm, double delta, double tau, Oracle f){
		double eta = getEta(gamma, norm);
		int ma = (int)(0.01 * Math.pow((norm / eta),2) * Math.log(1.0 / delta));
		int mb = (int)(0.01 * Math.pow((norm / eta),2) * Math.log(norm / (delta * gamma)));

		int m = 0;
		List<Set<Integer>> ls = new LinkedList<Set<Integer>>();
	
		ma = Math.min(N, ma);
		mb = Math.min(N, mb); 
		ls.add(getIndexSet(N,ma));
		
		for(int l = 1; l <= (int)(Math.log(N)/Math.log(2)) + 1; l++){
			m = (int)Math.min(mb, Math.pow(2, l-1));
			ls.add(getIndexSet((int)Math.pow(2, l-1), m));
		}
		ls.add(getIndexSet(N, m));
		return ls;
	}
	
	private static Set<Integer> getIndexSet(int domain, int num){
		int i = 0;
		int index;
		Set<Integer> s = new HashSet<Integer>();
		if(domain == 1){
			s.add(0);
		}
		else{
			Random rnd = new Random();
			while(i < num){
				index = rnd.nextInt(domain);
				if(!s.contains(index)){
					s.add(index);
					i++;
				}
			}
		}
		return s;
	}
	
	private static Set<Integer> getQ(List<Set<Integer>> abSets, int N){
		Set<Integer> q = new HashSet<Integer>();
		Set<Integer> union = new HashSet<Integer>();
		Set<Integer> a = abSets.get(0);
		int element = 0;
		for(int i = 1; i < abSets.size(); i++){
			for(Integer x : abSets.get(i)){
				union.add(x);
			}
		}
		for(Integer x : a){
			for(Integer y : union){
				element = (x - y) % N;
				if(element < 0)
					element += N;
				q.add(element);
			}
		}
			
		return q;
	}
	
	private static Map<Integer, Complex> getQueriesValues(Set<Integer> Q, Oracle f){
		Map<Integer, Complex> queries = new HashMap<Integer, Complex>();
		for(Integer q : Q){
			queries.put(q, f.query(q));
		}
		return queries;
	}
	
	private static List<Integer> fixedQueriesSFT(int N, double tau, List<Set<Integer>> abSets, Map<Integer, Complex> queries){
		List<Integer> coff = new LinkedList<Integer>();
		List<Delimiter> candidates = new LinkedList<Delimiter>();
		List<Delimiter> candidatesNext = new LinkedList<Delimiter>();
		Set<Integer> A = abSets.get(0);
		int ab = 0;
		int a = 0;
		int b = 0;
		
		candidatesNext.add(new Delimiter(0, N-1));

		for(int i = 0; i < (int)(Math.log(N)/Math.log(2)) + 1; i++){
			candidates.clear();
			candidates.addAll(candidatesNext);
			candidatesNext.clear();
			for(Delimiter d : candidates){
				a = d.getFirst();
				b = d.getSecond();

				ab = (int)Math.floor((double)(a + b) / 2);
				if((a <= ab) && (distinguishingAlgorithm(a, ab, tau, A, abSets.get(i + 1), queries, N))){			
					candidatesNext.add(new Delimiter(a, ab));
				}
				if((b >= ab+1) && (distinguishingAlgorithm(ab+1, b, tau, A, abSets.get(i + 1), queries, N))){
					candidatesNext.add(new Delimiter(ab+1, b));
				}
			}
		}
		for(Delimiter d : candidatesNext){
			if(distinguishingAlgorithm(d.getFirst(), d.getSecond(), tau, A, abSets.get(abSets.size()-1), queries, N))
				coff.add(d.getFirst());
		}
		return coff;
	}
	
	private static boolean distinguishingAlgorithm(int a, int b, double tau, Set<Integer> A, Set<Integer> B, Map<Integer, Complex> queries, int N){
		double est = 0;
		Complex sum = new Complex(0,0);
		Complex temp = new Complex(0,0);
		double weight = 0;
		double ab = Math.floor((a + b) / 2);
		int element = 0;
		for(Integer x : A){
			for(Integer y : B){
				element = (x - y) % N;
				if(element < 0)
					element += N;
				temp = ComplexOperations.mulComplex(chiFunction(ab, N, y), queries.get(element));
				sum = ComplexOperations.addComplex(sum, temp);
			}
			sum = ComplexOperations.mulComplex(1 / (double)B.size(), sum);
			weight += Math.pow(sum.getNorm(), 2);
		}
		est = (1 / (double)A.size()) * weight;
		
		if (est >= ((double)5/36) * tau)
			return true;
		return false;
	}
	
	public static Complex chiFunction(double alpha, int N, int x){
		Complex r = new Complex((2 * Math.PI * alpha * x)/N);
		return r;
	}
}
